package sort

/**
 * 快速排序
 */
func (this *Sort) QuickSort(arr []int) {

	length := len(arr)
	if length >= 2 {
		quickSortSub(arr)
	}
	return
}

func quickSortSub(arr []int) {

	// 获取切片长度
	length := len(arr)
	if length >= 2 {
		// 获取中间值
		point := findPoint(arr)
		small := arr[:point]
		big := arr[point+1:]
		quickSortSub(small)
		quickSortSub(big)
	}
}

func findPoint(arr []int) int {

	length := len(arr)

	begin := 0
	last := length - 1

	for j := begin; j < last; j++ {
		if arr[j] < arr[last] {
			arr[begin], arr[j] = arr[j], arr[begin]
			begin++
		}
	}
	arr[begin], arr[last] = arr[last], arr[begin]

	// 中间分割点
	return begin
}
